#!/usr/bin/env python3

class Node:
    def __init__(self, left=None, data=None, right=None):
        self.left = left
        self.data = data
        self.right = right


def findLCA(node, value1, value2, result=None):
    if node is None:
        return None

    if result is None:
        result = [False, False]

    if node.data == value1:
        result[0] = True
        return node

    if node.data == value2:
        result[1] = True
        return node

    left_lca = findLCA(node.left, value1, value2, result)
    right_lca = findLCA(node.right, value1, value2, result)

    if left_lca and right_lca:
        return node
    if left_lca is None and right_lca is not None:
        return right_lca
    elif left_lca is not None and right_lca is None:
        return left_lca
    else:
        return None
    


#               1
#             /   \
#            2     3
#           / \   / \
#          4   5 6   7
if __name__ == '__main__':
    node4 = Node(data=4)
    node5 = Node(data=5)
    node6 = Node(data=6)
    node7 = Node(data=7)
    node2 = Node(left=node4, data=2, right=node5)
    node3 = Node(left=node6, data=3, right=node7)
    node1 = Node(left=node2, data=1, right=node3)

    assert 2 == findLCA(node1, 4, 5).data
    assert 1 == findLCA(node1, 4, 6).data
    assert 2 == findLCA(node1, 2, 4).data
    
